//给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 
//
// 算法的时间复杂度应该为 O(log (m+n)) 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums1 = [1,3], nums2 = [2]
//输出：2.00000
//解释：合并数组 = [1,2,3] ，中位数 2
// 
//
// 示例 2： 
//
// 
//输入：nums1 = [1,2], nums2 = [3,4]
//输出：2.50000
//解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
// 
//
// 
//
// 
//
// 提示： 
//
// 
// nums1.length == m 
// nums2.length == n 
// 0 <= m <= 1000 
// 0 <= n <= 1000 
// 1 <= m + n <= 2000 
// -106 <= nums1[i], nums2[i] <= 106 
// 
// Related Topics 数组 二分查找 分治 
// 👍 4993 👎 0

package com.cute.leetcode.editor.cn;
public class MedianOfTwoSortedArrays {
    public static void main(String[] args) {
        Solution solution = new MedianOfTwoSortedArrays().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 两个数组合并之后保留重复元素
         * 时间复杂度要求为log(m + n)
         * 实际新建合并数组和模拟合并数组再求中位数的方法时间复杂度都是m+n
         * 只有使用二分法时时间复杂度才满足要求
         * 可以转换为寻找合并数组后的第k小个元素
         * 对k进行二分，每次从不同的数组中去舍去k/2个元素
         */
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int n = nums1.length;
            int m = nums2.length;
            //不论奇偶数都会求两次，奇数求两次也求出的是同样的值
            int k1 = (n + m + 1) / 2;
            int k2 = (n + m + 2) / 2;
            return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, k1) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, k2)) * 0.5;
        }

        private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
            int len1 = end1 - start1 + 1;
            int len2 = end2 - start2 + 1;

            //这里保证传进来的num1的长度是小的
            if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
            //说明数组1已经空了
            if (len1 == 0) return nums2[start2 + k - 1];
            //这里只需要比较并返回数组的第一个值即可
            if (k == 1) return Math.min(nums1[start1], nums2[start2]);

            //nums1中的start1开始处的第k/2个元素，如果长度不够就指向末尾
            int i = start1 + Math.min(len1, k / 2) - 1;
            //nums2中的start2开始处的第k/2个元素，如果长度不够就指向末尾
            int j = start2 + Math.min(len2, k / 2) - 1;
            if (nums1[i] > nums2[j])// 如果nums1中的元素要大，那说明可以舍去nums2中的部分元素
                return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
            else // 否则舍去nums1中的部分元素
                return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}